package com.leetcode.easy;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * @Classname SingleNumber
 * @Description 只出现一次的数字
 * @Date 2020/9/22 16:44
 * @Created by zfl
 */
public class SingleNumber {


    /**
     * @param nums
     * @return
     * TreeSet
     * TreeSet底层是基于TreeMap来实现的，所以底层结构也是红黑树，因为它和HashSet不同的是不需要重写HashCode()和equals()方法，
     * 因为它的去重是依靠比较器去重，由于结构是红黑树，故每次插入都会遍历来寻找节点插入位置，如果发现某个节点的值是一样的就直接覆盖。
     * TreeSet在保证元素唯一性的基础之上，还可以对元素进行排序。
     * 执行用时：21 ms, 在所有 Java 提交中击败了5.63%的用户
     * 内存消耗：39 MB, 在所有 Java 提交中击败了97.46%的用户
     */
    public static int singleNumber(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        Iterator it = set.iterator();
        return (int) it.next();
    }

    /**
     * @param nums
     * @return
     * HashSet
     * HashSet的add()/remove()/contains()方法都是直接调用HashMap实现的，保证唯一性是调用HashMap的put()方法，而put()方法有一行逻辑
     * 如果哈希值和key都一样，就会直接拿新值覆盖旧值，HashSet就是利用这个特性来保证唯一性的。所以当用来存放对象时要重写HashCode()和equals()方法。
     * 执行用时：10 ms, 在所有 Java 提交中击败了16.20%的用户
     * 内存消耗：39.2 MB, 在所有 Java 提交中击败了94.16%的用户
     */
    public static int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        Iterator it = set.iterator();
        return (int) it.next();
    }

    /**
     * @param nums
     * @return
     * 异或：
     * 任何数和0做异或运算，结果仍然是原来的数，即a^0=a
     * 任何数和起自身做异或运算，结果是0，即a^a=0
     * 异或运算满足交换律和结合律，即a^b^a=a^a^b=b
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.68%的用户
     * 内存消耗：40 MB, 在所有 Java 提交中击败了23.57%     的用户
     */
    public static int singleNumber3(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}
